退職で、高知大学の私のホームページが閉鎖されたので、ここに移しました。
ここでは、Hopf 代数のコホモロジーのコンピュータを使った計算法を紹介します。
Hopf 代数のコホモロジーは Minimal Resolution や cobar construction を使えば原理的には計算できますが、
ちょっと複雑なHopf 代数では手計算は困難です。mod p Steenrod algebra Ap の cohomology を計算する為に
J. Peter May が導入した May Spectral Sequence を使うのが有力な方法です。この計算は二つの計算部分に
分かれます。一つは微分代数のホモロジーを計算する部分で、もう一つは微分を計算する
部分です。若い頃、手計算で mod p Steenrod algebra Ap の cohomology を計算していましたが、大変なので、
mod 2 Steenrod algebra A2 の cohomology を計算機で計算することを考えました。
このためには二つソフトを作れば良いです。一般的に微分代数のホモロジー
を計算する all.exe と名付けたソフトと cobar construction の計算を
自動的に実行してくれる diff.exe と名付けたソフトです。これらのソフトは20年ぐらい前に作りました。
その時は使えるコンピュータの性能が低く、リー群 E7の Z2 cohomology の cohomology ぐらいの計算量の比較的少ない
計算は完全にできましたが、mod 2 Steenrod algebra A2 の cohomology など私が計算したい計算は、
望みの計算をすることが出来ませんでした。
やっと、64 ビットのパソコンが販売され、誰でも購入でき、予算が削られ死にかかっている地方大学の教育学部にいる
私でも、大きな記憶容量を使えるようになってきたので、記憶容量の問題は解決しつつあります。しかし、パソコンでは、まだ最大24ギガバイトですので、私がしたかった計算は不可能です。多分、テラバイト単位の記憶容量が必要です。
特に diff.exe は計算時間は、まだ解決していなくて、簡単な問題は良いですが、複雑な微分の計算などは、
パソコンの前に座って待っていても、答えはすぐには出ません。
しかし、使っていないコンピュータがあれば、それを利用すれば、コンピュータが時間は滅茶苦茶掛かります(
個々の場合、数時間なのか、数日なのか、数カ月なのか、数年なのか・・・、私にも時間の評価はできません)が、
ほぼ勝手に計算してくれます。従って、パソコンで計算する場合には、diff.exe だけでも原理的には計算できますが、
Martin C. Tangora や Osamu Nakamura がmod 2 Steenrod algebra A2 の cohomology の計算でしたように、
Lie 群の cohomology のような各種 Hopf algebra の Cotor の計算でも、
Manipulative Methods や matric Massey products method や application of effect of squaring operations
in May spectral sequence といった種々の手法を使っても計算できない場合の非常手段として、
使うのが良いと思います。
私も3月末で定年になり、残された時間も少なくなってきました。
ソースコードを公表しますから、興味のある方は使ってみてください。以下、ソフトの説明をします。
May Spectral Sequence とは





微分代数のコホモロジーを計算するプログラムのアルゴリズム
all.exe は線形代数の範囲の知識でアルゴリズムが作れます。正しい Ker d / Im d の基底と既に得られている
indecomposable elements と defining relations から作られる基底との比較をすることにより
その差を比較しているだけの単純なものです。
具体的な例によって微分代数のコホモロジーを計算するプログラムのアルゴリズムを説明します。
以下で考える微分代数の構造が次のように与えられているとします。
generators が degree - homological dimension, homological dimension, weight, name, differential の順に並べた時
| 0 | 1 | 0 | 0 | E |
| 1 | 1 | 0 | 1 | E |
| 3 | 1 | 0 | 2 | E |
| 4 | 2 | 2 | 8 | 1^3+0^2*2 |
| 7 | 1 | 0 | 3 | E |
| 7 | 2 | 2 | 9 | 0*2^2 |
| 10 | 2 | 2 | 10 | 2^3+1^2*3 |
| 12 | 2 | 4 | 11 | 1*10+3*8 |
| 15 | 1 | 0 | 4 | E |
| 16 | 2 | 2 | 12 | 1*3^2 |
であり、それらの間の relations が degree - homological dimension, homological dimension, weight, relation の
順に並べた時, degree - homological dimension <= 20 の範囲で
| 1 | 2 | 0 | 0*1 |
| 4 | 2 | 0 | 1*2 |
| 7 | 3 | 2 | 2*8+0*9 |
| 10 | 2 | 0 | 2*3 |
| 10 | 3 | 2 | 2*9+0*10 |
| 14 | 3 | 2 | 3*9 |
| 14 | 4 | 4 | 9^2+8*10+1^2*11 |
| 16 | 3 | 2 | 0*12 |
| 17 | 3 | 2 | 3*10+1*12 |
| 20 | 4 | 4 | 8*12+1*3*11 |
であるとします。ここで、generators の name は普通 h0とか h0(1)とか b02 ですが、Memory を稼ぐために単なる
数字にしています。また、generators のリストの E は微分が 0 であることを示しています。
このような可換微分代数のコホモロジーを計算することを考えます。
homological dimension の小さい順、degree - homological dimension の小さい順、weight の小さい順に順番に計算していきます。
以下、degree - homological dimension, homological dimension, weight を deg, s, wht と略記します。
今、s=5, deg=15, wht=4 を計算する番になったとします。
generators を使って作られる形式的基底は
- 0^2*2*11 0^2*1*2*10+0^2*2*8*3
- 1^3*11 1^3*8*3+1^4*10
- 1*8*10 0^2*1*2*10+1*2^3*8+1^3*8*3+1^4*10
- 1*9^2 E
- 8^2*3 E
です。
これらを含む形式的 relations は
- 1*9^2+1*8*10+1^3*11 <--- 9^2+8*10+1^2*11
があります。
これで行列を作ると
- 1*9^2:F name=: body=1*9^2:F -> body=1*8*10:F -> body=1^3*11:F ->
となり、rank を求めるときと同様の処理をすると
- 1*9^2:U name=: body=1*9^2:U -> body=1*8*10:Z -> body=1^3*11:Z ->
となるので、1*8*10 と 1^3*11 を基底の要素と考え、1*9^2 は 1*8*10+1^3*11 と表されるので、
s=5, deg=15, wht=4 の基底は
- 0^2*2*11 0^2*1*2*10+0^2*2*8*3
- 1^3*11 1^3*8*3+1^4*10
- 1*8*10 0^2*1*2*10+1*2^3*8+1^3*8*3+1^4*10
- 8^2*3 E
です。何を言っているか分からないと思いますから、別の例で説明します。
形式的なrelations が
- x : a+b+c = 0
- y : a+b = 0
- z : c = 0
であれば、
| a | b | c |
| x : | 1 | 1 | 1 |
| y : | 1 | 1 | 0 |
| z : | 0 | 0 | 1 |
という行列を作り、一行目を二行目に加え
| a | b | c |
| x : | 1 | 1 | 1 |
| x+y : | 0 | 0 | 1 |
| z : | 0 | 0 | 1 |
二行目を一行目と三行目に加え
| a | b | c |
| y : | 1 | 1 | 0 |
| x+y : | 0 | 0 | 1 |
| x+y+z : | 0 | 0 | 0 |
とします。今、係数は mod 2 で考えます。この操作を rank を求める操作と呼んでいます。
整理された relations は a = b と c = 0 です。このような処理が必要なのは、
一般的に relations の集合がブレブナー基底になっていないからです。
微分の部分も基底を求めて、整理しなければなりません。
例えば、 0^2*1*2*10+0^2*2*8*3 について考えると、 0^2*1*2*10 に関連する形式的 relations は
です。従って、 0^2*1*2*10 は 0 です。0^2*2*8*3 に関連する形式的 relations は
です。従って、0^2*1*2*10 も 0 です。従って、0^2*2*11 E となります。
このような計算を繰り返すと
s=5, deg=15, wht=4 の base elements は
| 0^2*2*11 | E |
| 1^3*11 | 1^3*8*3+1^4*10 |
| 1*8*10 | 1^3*8*3+1^4*10 |
| 8^2*3 | E |
となります。これを target にセットします。
次に、s=4, deg=16, wht=2 の generators を使って作られる形式的基底は
- 8*11 0^2*2*11+1*8*10+1^3*11+8^2*3
です。
これらを含む形式的 relations はありません。
同様にして、微分を計算すると
s=4, deg=16, wht=2 の base elements は
- 8*11 0^2*2*11+1*8*10+1^3*11+8^2*3
となります。これを source にセットします。
target の情報を使って行列を作り、rannk の処理をして cocycle を求めます。即ち、
| 1^3*8*3 | 1^4*10 |
| 0^2*2*11 : | 0 | 0 |
| 1^3*11 : | 1 | 1 |
| 1*8*10 : | 1 | 1 |
| 8^2*3 : | 0 | 0 |
から、
| 1^3*8*3 | 1^4*10 |
| 0^2*2*11 : | 0 | 0 |
| 1^3*11 : | 1 | 1 |
| 1*8*10+1^3*11 : | 0 | 0 |
| 8^2*3 : | 0 | 0 |
と変形します。 cocycle は 0^2*2*11 と 1*8*10+1^3*11 と 8^2*3 になります。
これを二分木にセットします。
- cocycle -> 0^2*2*11:F->1*8*10+1^3*11:F->8^2*3:F->
コンピュータ内部では、処理した後の行列は
- 1^3*8*3:F : name= 1^3*11: body=1^3*8*3:F -> body=1^4*10:F ->
となります。
次に、今までの計算で既に得られている indecomposable elements を使って計算すると
s=5, deg=15, wht=4 の形式的基底は、base, representative の順に
- 0^2*9 0^2*2*11
- 1*17 1*8*10+1^3*11
- 3*16 8^2*3
です。defining relations を使って同様に基底を求めると
- 0^2*9 0^2*2*11
- 1*17 1*8*10+1^3*11
- 3*16 8^2*3
です。
同様に representative を修正すると
- 0^2*9 0^2*2*11
- 1*17 1*8*10+1^3*11
- 3*16 8^2*3
です。
これを配列 b_chain[] にセットします。二分木は上で求めた cocycle を使います。
- b_chain[0] -> name=0^2*9: body=0^2*2*11:F->
- b_chain[1] -> name=1*17: body=1*8*10+1^3*11:F->
- b_chain[2] -> name=3*16: body=8^2*3:F->
となります。
source の情報
- 8*11 0^2*2*11+1*8*10+1^3*11+8^2*3
から行列を作り、ランクの処理をする。二分木は cocycle を使います。
- 0^2*2*11:F name=8*11: body=0^2*2*11:F->body=1*8*10+1^3*11:F->body=8^2*3:F->
となります。
この行列の主対角成分に \verb?'B'? の符号を付けます。
- 0^2*2*11:B name=8*11: body=0^2*2*11:B->body=1*8*10+1^3*11:F->body=8^2*3:F->
これは、0^2*2*11 は d(8*11) によって 1*8*10+1^3*11 と 8^2*3 の和で書けることを意味しています。
配列 b_chain[] に含まれるこの行列の主対角要素をその行の他の要素で置き換える。
- b_chain[0] -> name=0^2*9: body=1*8*10+1^3*11:F->body=8^2*3:F->
- b_chain[1] -> name=1*17: body=1*8*10+1^3*11:F->
- b_chain[2] -> name=3*16: body=8^2*3:F->
となります。
b_chain[] から行列を作り、rank の処理をする。
コサイクルを配列 d[] にセットする。d[] が defininng relations である。
行列は
- 8^2*3:F name=1*17+0^2*9: body=8^2*3:F->
- 1*8*10+1^3*11:F name=1*17: body=1*8*10+1^3*11:F->
となり、d[] は
です。
従って、新しい defininng relations 3*16+1*17+0^2*9 が現れます。
上の行列の対角要素に対応する cocycle に 'U' の符号を付ける。
cocycle を調べ、flag=='F' の cocycles が indecomposable elements である。
今の場合
- cocycle -> 0^2*2*11:B->1*8*10+1^3*11:U->8^2*3:U->
なので、indecomposable elements はありません。
このような処理をするプログラムを作れば、微分代数のコホモロジーを計算するソフトが作れます。
May Spectral Sequence の微分を計算するプログラムのアルゴリズム
次に、 May Spectral Sequence の differentials を計算するソフトを具体的な計算例を使って紹介をします。
d2(h0(1)) = h0h2^2 を cobar construction で計算してみます。
h0(1) の May Complex での representative は R02R12+R11R03 なので
d([2/2^2]+[1^2/3]) から始めます。これは computer が使用する記憶容量を少なくするために d([ξ2/ξ2^2]+[ξ1^2/ξ3]) を
省略した表現です。以下、同様です。
結果は
[1^2/1/2^2]+[2/1^4/1^2]+[1^2/1^4/2]+[1^2/2^2/1]
です。
まず [1^2/1/2^2]+[1^2/2^2/1] に注目します。これを消すためには
d([1^2/1*2^2]) を計算すれば良いです。
結果は
[2/1^4/1^2]+[1^2/1^4/2]+[1^2/1^5/1^2]+[1^2/1^4/1^3]
です。
次に [2/1^4/1^2]+[1^2/1^4/2] に注目します。これを消すためには
d([1^4*2/1^2]+[1^4/1^2*2]+[1^6/2]) を計算すれば良いです。
結果は
[1^2/1^4/1^3]+[1^6/1/1^2]+[1^4/1^2/1^3]+[1^6/1^2/1]+[1^4/1^4/1]
です。
次に
[1^2/1^4/1^3]+[1^6/1/1^2]+[1^4/1^2/1^3]+[1^6/1^2/1]
に注目します。これを消すためには
d([1^6/1^3]) を計算すれば良いです。
結果は
[1^4/1^4/1]
です。
これで答え d2(h0(1)) = h0h2^2 が求まりました。
この計算過程を計算機にやらせるためには、一般にはたくさんある brackets のどれから手を付けるかと
選び出した brackets はどうすれば消去できるかを考える必要があります。
どれから手を付けるかを決めるには、cobar construction の brackets に順序を導入すればいいです。
当然、まず、weight の大きいものから順に手を付けます。
weight が同じなら、ξn^{2^p} の形の要素の積に分解したときのその個数に注目して順序を入れます。
今の例の場合は
[1^2/1/2^2]+[2/1^4/1^2]+[1^2/1^4/2]+[1^2/2^2/1]
のうち、
[1^2/1/2^2]+[1^2/2^2/1] には、2^2 が一個、1^2 が一個、1 が一個あり、
[2/1^4/1^2]+[1^2/1^4/2] には、2 が一個、1^4 が一個、1^2 が一個あります。
これらをそれぞれ
- sub=2 * pow=1 num=1
- sub=1 * pow=1 num=1 pow=0 num=1
と
- sub=2 * pow=0 num=1
- sub=1 * pow=2 num=1 pow=1 num=1
で表現することにします。これを invariant と呼ぶことにします。
これを辞書式に比較します。
今の場合、sub=2 と sub=2 だから同じ、次の pow=1 と pow=0 で上のほうが大きいとします。
invariant の一番大きい brackets を集めるとそれを調べて、それを消去するための方法を考えます。
上の例では
[1^2/1/2^2]+[1^2/2^2/1]
に注目し、これを消すためには
d([1^2/1*2^2])
を計算すれば良かったのですが、これを機械的に見つける方法として、まず
[1^2/1/2^2] を調べます。最後の 2^2 にまず注目します。
これが単純な ξn^{2^p} の形でなければ、次の bracket を調べます。
単純な ξn^{2^p} の形なら、次の項の 1 と 2^2 を比較します。それぞれの invariant の最初の sub と pow を
比べます。それぞれ sub1, pow1 と sub2, pow2 としたとき、sub1 > sub2 または sub1=sub2 かつ pow1 < pow2 なら
merge 可能であるとします。
今の場合、sub1=1, pow1=0, sub2=2, pow2=1 です。sub1 < sub2 なので merge 不可能です。
更に、この場合、1 は単純な ξn^{2^p} の形なので、一つ前の 1^2 と merge 可能か調べます。
今の場合、sub1=1, pow1=1, sub2=1, pow2=0 です。sub1=sub2, pow1 > pow2 なので merge 不可能です。
更に、1^2 が単純な ξn^{2^p} の形なので更にひとつ前の項と比較しますが今の場合、bracket が終わったので
[1^2/1/2^2] からは候補を選びません。
従って、次の bracket を調べます。
[1^2/2^2/1] の最後の項は 1 で単純な ξn^{2^p} の形なので、一つ前の 2^2 と merge 可能か調べます。
今の場合、sub1=2, pow1=1, sub2=1, pow2=0 です。sub1 > sub2 なので merge 可能です。
merge 可能な対が見つかるとこれを併合した
[1^2/1*2^2] を候補者とします。
次に [2/1^4/1^2]+[1^2/1^4/2] に注目し、これを消すためには
d([1^4*2/1^2]+[1^4/1^2*2]+[1^6/2])
を計算しました。
まず [2/1^4/1^2] を調べます。1^2 は単純ですが、1^4 とは merge 不可能です。1^4 は単純で、2 とは sub1 > sub2 なので
merge 可能です。
従って、2 と 1^4 を併合して
[1^4*2/1^2] が候補者になります。更に、2 と 1^2 が sub1 > sub2 で merge 可能なので、2 と 1^2 を併合して
[1^4/1^2*2] も候補者とします。
次に、
[1^2/1^4/2] を調べます。2 は単純ですが、1^4 とは merge 不可能です。1^4 は単純で、1^2 とは
sub1 = sub2, pow1 < pow2 なので merge 可能です。
従って、1^2 と 1^4 を併合して
[1^6/2] が候補者になります。1^2 と 2 とは merge 不可能です。これで候補者
[1^4*2/1^2]+[1^4/1^2*2]+[1^6/2] が見つかりました。
最後に、
[1^2/1^4/1^3]+[1^6/1/1^2]+[1^4/1^2/1^3]+[1^6/1^2/1]
に注目し、これを消すためには
d([1^6/1^3])
を計算しました。
まず [1^2/1^4/1^3] を調べます。最後の項 1^3 は単純ではないので、候補者は選べません。
次の [1^6/1/1^2] は、1^2 が単純で、1 と 1^2 とは sub1 = sub2, pow1 < pow2 なので merge 可能です。従って、
1 と 1^2 を併合して [1^6/1^3] が候補者になります。
次の [1^4/1^2/1^3] は、最後の項 1^3 は単純ではないので、候補者は選べません。
最後の [1^6/1^2/1] は、1^2 と 1 は sub1 = sub2, pow1 > pow2 なので merge 不可能で、1^6 と 1^2 も
sub1 = sub2, pow1 > pow2 なので merge 不可能です。
従って、候補者は作れません。これですべての候補者 [1^6/1^3] が見つかりました。
この方法で invariant が小さくなっていくことを証明すれば、無限ループに陥ることがないことを示すことが出来ます。
唯、この方法だけでは自動的に最終結果まで辿り着きません。
d4(h0(1)b12) = 0 について考えてみます。
h0(1)b12 の代表元は (R02R12+R11R03)R12R12
なので、
[2/2^2/2^2/2^2]+[1^2/3/2^2/2^2] を入力すると、 weight=2 の
R31R11R11R11R03+R21R21R21R11R03+R21R21R01R12R12+R31R11R11R21R20+R21R21R21R12R02
で、停止します。これを消去するのに
R11R11R11R04+R11R11R02R13+R21R21R12R03
を入力する必要があります。すると weight=1 の
R21R11R11R01R22+R31R21R21R11R02
で、停止します。これを消去するのに
R21R11R02R22
を入力する必要があります。すると weight=0 の
R31R31R11R11R01
で、停止します。これを消去するのに
R31R31R11R02
を入力する必要があります。
すると すべて消滅します。このように人間が介入する
必要があります。この部分を自動化することを考えます。
R31R11R11R11R03+R21R21R21R11R03+R21R21R01R12R12+R31R11R11R12R20+R21R21R21R12R02
から
R11R11R11R04+R11R11R02R13+R21R21R12R03
を選び出す方法は次のようにします。
May Complex の differential で消去することを考えます。
まずこれらに関係する微分をすべて集めます。
重複を除いて関連する微分を集める方法は
R31R11R11R11R03, R21R21R21R11R03, R21R21R01R12R12,
R31R11R11R12R20,R21R21R21R12R02,
をスタックと二分木にセットする。
スタックが空でない間は
スタックから項を取り出し、それを含む微分たちが無いか調べ、
あれば微分の集合に追加する。
その微分の項で二分木にセットされていないものをスタックに積む
これで、すべての関連する微分を集めることが出来る。
今の場合、
- d(R11R11R11R04) = R11R11R11(R01R13+R02R22+R03R31)
- d(R21R21R03R12) = R21R21(R01R12+R02R21)R12+R21R21R03(R21R11)
- d(R11R11R02R13) = R11R11(R01R11)R13+R11R11R02(R11R22+R12R31)
である。
これらの一次結合で
R31R11R11R11R03+R21R21R21R11R03
+R21R21R01R12R12+R31R11R11R12R20+R21R21R21R12R02
が作れるかを調べる。作れれば、それが候補者になる。
必要な微分を選ぶ方法は、今の場合
- x1+x3 = 0
- x1+x3 = 0
- x1 = 1
- x2 = 1
- x2 = 1
- x3 = 1
- x2 = 1
なる連立方程式を解けばいい。
これを解き、
x1=1, x2=1, x3=1 をうる。これで
R11R11R11R04+R11R11R02R13+R21R21R12R03
が候補者になる。
このように完全に連立方程式が解けるときだけ、候補者を自動的に生成するという方法を組み込むことにより、かなりの部分自動化できます。しかし、これだけでは完全には自動化できません。
部分的な情報で候補者を生成した場合は、無限ループに陥らないようにするのは厄介ですし、高次の微分の情報やrelations の情報が必要な場合があります。このような場合は、人間が介入して計算を続けるほうが安全だし、プログラミングが複雑になりません。
これの方法を実現したのが diff.exe というソフトです。
以下のプログラムは何度も何度も書き直したので、古い C 言語の断片と C++ の断片が混ざっています。ワークステーションで毎日、夕方になれば、プログラムを止めなければならなかった時の工夫など、今では意味のない断片も消去せず残っています。メモリを効果的に使えるよう vector などを使った、最新の C++ のプログラムに修正すべきですが、二十数年、いつまでたっても欲しい結果が得られないので、意欲がわかなくなりました。パソコンで数テラバイトのメモリが使えるようになれば、本格的に作り直します。(尤もそれまで私が活きていればですが。)今は、各種パズルやゲームのプログラミングに興味が移っていて、その方が人様の役に立つように思います。誰かのお役に立つなら自由にご利用下さい。
微分代数のコホモロジーを計算するプログラム all.exe のソースコード
all.cpp のダウンロ ード
all.h のダウンロ ード
May Spectral Sequence の微分を計算するプログラム diff.exe のソースコード
diff.cpp のダウンロ ード
diff.h のダウンロ ード
diff.exe を mod 2 Steenrod algebra 以外で使う場合の注意
例えば、リー群 E8の Z2 cohomology の cohomology の場合


なので、diff.exe のあるフォルダに gen.dat という名前で
3 3 1 16 E
5 5 1 8 E
9 9 1 4 E
15 15 2 4 3/3^4+5/5^2+9/3^2
17 17 1 2 E
23 23 2 2 3/5^4+5/9^2+17/3^2
27 27 2 2 3/3^8+9/9^2+17/5^2
29 29 2 2 5/3^8+9/5^4+17/3^4
元の名前、degree, weight, 何乗すればゼロになるか、coproduct の本体を並べたファイルを作り、置いておきます。
E は primitive element であることを意味します。
mod 2 Steenrod algebra の場合、
1 1 1 0 E
2 3 2 0 1^2/1
3 7 3 0 1^4/2+2^2/1
4 15 4 0 1^8/3+2^4/2+3^2/1
5 31 5 0 1^16/4+2^8/3+3^4/2+4^2/1
6 63 6 0 1^32/5+2^16/4+3^8/3+4^4/2+5^2/1
7 127 7 0 1^64/6+2^32/5+3^16/4+4^8/3+5^4/2+6^2/1
というファイルを置いておいてもいいです。 「何乗すればゼロになるか」の値が0なのは、何乗しても0にならないことを
意味しています。
May Complex の表現で R2:3R2:3R3:5R1:15R0:23R0:23 と表示されたら、それは
[3^4/3^4/5^8/15^2/23/23] のことです。
高知大学名誉教授
中村 治
osamu@mg.pikara.ne.jp